import collections


class Solution(object):
    def networkDelayTime(self, times, n, k):
        """
        :type times: List[List[int]]
        :type n: int
        :type k: int
        :rtype: int
        """
        P = [-1] * n
        edge = collections.defaultdict(dict)
        for time in times:
            edge[time[0]][time[1]] = time[2]
        P[k - 1] = 0

        def search(point):
            for next_point in edge[point]:
                if P[next_point - 1] == -1 or P[next_point - 1] > P[point - 1] + edge[point][next_point]:
                    P[next_point - 1] = P[point - 1] + edge[point][next_point]
                    search(next_point)

        search(k)
        min_time = 0
        for num in P:
            if num == -1:
                return -1
            min_time = max(min_time, num)
        return min_time


data = Solution()
times = [[2, 1, 1], [2, 3, 1], [3, 4, 1]]
n = 4
k = 2
print(data.networkDelayTime(times, n, k))
